λ¬Έμ
μΈλ‘ λ μ€, κ°λ‘λ‘ Nκ°μ μΉΈμΌλ‘ μ΄λ£¨μ΄μ§ νκ° μλ€. 첫째 μ€μ κ° μΉΈμλ μ μ 1, 2, β¦, Nμ΄ μ°¨λ‘λλ‘ λ€μ΄ μκ³ λμ§Έ μ€μ κ° μΉΈμλ 1μ΄μ Nμ΄νμΈ μ μκ° λ€μ΄ μλ€. 첫째 μ€μμ μ«μλ₯Ό μ μ ν λ½μΌλ©΄, κ·Έ λ½ν μ μλ€μ΄ μ΄λ£¨λ μ§ν©κ³Ό, λ½ν μ μλ€μ λ°λ‘ λ°μ λμ§Έ μ€μ λ€μ΄μλ μ μλ€μ΄ μ΄λ£¨λ μ§ν©μ΄ μΌμΉνλ€. μ΄λ¬ν 쑰건μ λ§μ‘±μν€λλ‘ μ μλ€μ λ½λ, μ΅λλ‘ λ§μ΄ λ½λ λ°©λ²μ μ°Ύλ νλ‘κ·Έλ¨μ μμ±νμμ€. μλ₯Ό λ€μ΄, N=7μΈ κ²½μ° μλμ κ°μ΄ νκ° μ£Όμ΄μ‘λ€κ³ νμ.
μ΄ κ²½μ°μλ 첫째 μ€μμ 1, 3, 5λ₯Ό λ½λ κ²μ΄ λ΅μ΄λ€. 첫째 μ€μ 1, 3, 5λ°μλ κ°κ° 3, 1, 5κ° μμΌλ©° λ μ§ν©μ μΌμΉνλ€. μ΄λ μ§ν©μ ν¬κΈ°λ 3μ΄λ€. λ§μ½ 첫째 μ€μμ 1κ³Ό 3μ λ½μΌλ©΄, μ΄λ€ λ°λ‘ λ°μλ μ μ 3κ³Ό 1μ΄ μμΌλ―λ‘ λ μ§ν©μ΄ μΌμΉνλ€. κ·Έλ¬λ, μ΄ κ²½μ°μ λ½ν μ μμ κ°μλ μ΅λκ° μλλ―λ‘ λ΅μ΄ λ μ μλ€.
μ λ ₯
- 첫째 μ€μλ N(1β€Nβ€100)μ λνλ΄λ μ μ νλκ° μ£Όμ΄μ§λ€. κ·Έ λ€μ μ€λΆν°λ νμ λμ§Έ μ€μ λ€μ΄κ°λ μ μλ€μ΄ μμλλ‘ ν μ€μ νλμ© μ λ ₯λλ€.
μΆλ ₯
- 첫째 μ€μ λ½ν μ μλ€μ κ°μλ₯Ό μΆλ ₯νκ³ , κ·Έ λ€μ μ€λΆν°λ λ½ν μ μλ€μ μμ μλΆν° ν° μμ μμλ‘ ν μ€μ νλμ© μΆλ ₯νλ€.
π Logic
class Graph {
int[] graph;
int[] visited;
PriorityQueue<Integer> path = new PriorityQueue<>();
}
- μ
λ ₯λλ μ«μλ€μ μ μ₯νλ
graphλ°°μ΄, κ° μ μ μ λ°©λ¬Έμ¬λΆλ₯Ό μ μ₯νλvisitedλ°°μ΄, μ¬μ΄ν΄μ μ΄λ£¨λ μ μ λ€μ μ μ₯νλpathμ°μ μμ ν
public void solution() {
for (int i=1; i<graph.length; i++) {
if (dfs(i, i) == 1) {
path.add(i);
}
visited = new int[graph.length];
}
printList();
}
- κ° μ μ μ μμμΌλ‘ νμ¬,
dfsμ 리ν΄κ°μΌλ‘ μ¬μ΄ν΄μ μ‘΄μ¬μ¬λΆ νμΈ - μ‘΄μ¬νλ κ²½μ°,
pathμ°μ μμ νμ μ μ₯ - λ°©λ¬Έ μ¬λΆλ₯Ό μ μ₯νλ
visitedμ΄κΈ°ν
public int dfs (int start, int end) {
if (visited[end] == 0) {
visited[end] = 1;
return dfs(start, graph[end]);
}
else {
return (start == end) ? 1 : 0;
}
}
- μμμ , μμμ μμ μ΄μ΄μ§λ μ μ μ μΈμλ‘ λ°μ, λ°©λ¬Έμ¬λΆλ₯Ό νμΈνκ³ λ°©λ¬Έ 체ν¬
-
μ΄μ΄μ§λ μ μ μ΄ λ°©λ¬Έν κ²½μ°, μμμ κ³Ό λμΌνμ§ νμΈ
- λμΌν κ²½μ°, μ¬μ΄ν΄μ΄ μ‘΄μ¬ β 1 λ°ν
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Graph {
int[] graph;
int[] visited;
PriorityQueue<Integer> path = new PriorityQueue<>();
public Graph(int size) {
graph = new int[size+1];
visited = new int[size+1];
}
public void AddElement(int idx, int item) {
graph[idx] = item;
}
public void solution() {
for (int i=1; i<graph.length; i++) {
if (dfs(i, i) == 1) {
path.add(i);
}
visited = new int[graph.length];
}
printList();
}
public int dfs (int start, int end) {
if (visited[end] == 0) {
visited[end] = 1;
return dfs(start, graph[end]);
}
else {
return (start == end) ? 1 : 0;
}
}
public void printList() {
System.out.println(path.size());
for (int t : path)
System.out.println(t);
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
Graph g = new Graph(T);
for (int i=1; i<=T; i++) {
g.AddElement(i, sc.nextInt());
}
g.solution();
sc.close();
}
}
βοΈ Review
- μ μ C++λ‘ νΌ λ¬Έμ μλλ°, JAVAλ‘ λ³ννλ©΄μ λ€μ ν λ² μμ΄λμ΄λ₯Ό μκ°ν΄λ³΄μλ€.
- κ·Έλν λ¬Έμ μ΄κΈ° λλ¬Έμ, μ ν₯μ΄λ 무ν₯μ΄λ μ΄μ¨λ κ·Έλνλ‘μ ννμ΄ κ°λ₯νλ€λ μλ―ΈλΌκ³ μκ°ν΄ μ μ κ°μ μΈμ μ 보λ₯Ό νννκ³ μ΄λ₯Ό κ·Έλ € μμ΄λμ΄λ₯Ό μκ°ν΄λ³΄μλ€.
-
μ¬μ΄ν΄μ΄ μ‘΄μ¬νλ κ²½μ°, μ¬μ΄ν΄μ νμ±νλ PATHκ° μ λ΅μ΄ λλ€κ³ μκ°νλ€.
- λ°©λ¬Έν μ μ μ λ€μ λ°©λ¬Ένλ κ²½μ°λ‘ ꡬννλ €κ³ νμΌλ, λ°©λ¬Έ μ¬λΆ λ³κ²½κ³Ό νμΈ μμ μμ λ§νλ€.